Wiggle sort II [Tri Partition]¶
Time: O(NLogN); Space: O(N); medium
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]…
Example 1:
Input: nums = [1, 5, 1, 1, 6, 4]
Output: [1, 4, 1, 5, 1, 6] (one possible answer)
Example 2:
Input: nums = [1, 3, 2, 2, 3, 1]
Output: [2, 3, 1, 3, 1, 2] (one possible answer)
Note:
You may assume all input has valid answer.
Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?
Sorting and reoder solution. (92ms)
[20]:
class Solution1(object):
"""
Time: O(NlogN)
Space: O(N)
"""
def wiggleSort(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
nums.sort()
med = (len(nums) - 1) // 2
nums[::2], nums[1::2] = nums[med::-1], nums[:med:-1]
[21]:
s = Solution1()
nums = [1, 5, 1, 1, 6, 4]
s.wiggleSort(nums)
assert nums == [1, 6, 1, 5, 1, 4]
nums = [1, 3, 2, 2, 3, 1]
s.wiggleSort(nums)
assert nums == [2, 3, 1, 3, 1, 2]
[22]:
class Solution2(object):
def wiggleSort(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
tmp = nums[:]
tmp.sort()
n = len(nums)
left = (n - 1) // 2
right = n - 1
for i in range(n):
if i % 2 == 0:
nums[i] = tmp[left]
left -= 1
else:
nums[i] = tmp[right]
right -= 1
[23]:
s = Solution2()
nums = [1, 5, 1, 1, 6, 4]
s.wiggleSort(nums)
assert nums == [1, 6, 1, 5, 1, 4]
nums = [1, 3, 2, 2, 3, 1]
s.wiggleSort(nums)
assert nums == [2, 3, 1, 3, 1, 2]
[24]:
from random import randint
class Solution3(object):
"""
Tri Partition (aka Dutch National Flag Problem) with virtual index solution. (TLE)
Time: O(N) ~ O(N^2)
Space: O(1)
"""
def wiggleSort(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
def findKthLargest(nums, k):
left, right = 0, len(nums) - 1
while left <= right:
pivot_idx = randint(left, right)
new_pivot_idx = partitionAroundPivot(left, right, pivot_idx, nums)
if new_pivot_idx == k - 1:
return nums[new_pivot_idx]
elif new_pivot_idx > k - 1:
right = new_pivot_idx - 1
else: # new_pivot_idx < k - 1.
left = new_pivot_idx + 1
def partitionAroundPivot(left, right, pivot_idx, nums):
pivot_value = nums[pivot_idx]
new_pivot_idx = left
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
for i in range(left, right):
if nums[i] > pivot_value:
nums[i], nums[new_pivot_idx] = nums[new_pivot_idx], nums[i]
new_pivot_idx += 1
nums[right], nums[new_pivot_idx] = nums[new_pivot_idx], nums[right]
return new_pivot_idx
def reversedTriPartitionWithVI(nums, val):
def idx(i, N):
return (1 + 2 * (i)) % N
N = len(nums) // 2 * 2 + 1
i, j, n = 0, 0, len(nums) - 1
while j <= n:
if nums[idx(j, N)] > val:
nums[idx(i, N)], nums[idx(j, N)] = nums[idx(j, N)], nums[idx(i, N)]
i += 1
j += 1
elif nums[idx(j, N)] < val:
nums[idx(j, N)], nums[idx(n, N)] = nums[idx(n, N)], nums[idx(j, N)]
n -= 1
else:
j += 1
mid = (len(nums) - 1) // 2
findKthLargest(nums, mid + 1)
reversedTriPartitionWithVI(nums, nums[mid])
[25]:
s = Solution3()
nums = [1, 5, 1, 1, 6, 4]
s.wiggleSort(nums)
# print(nums)
assert nums == [1, 6, 1, 5, 1, 4] or [1, 5, 1, 6, 1, 4]
nums = [1, 3, 2, 2, 3, 1]
s.wiggleSort(nums)
# print(nums)
assert nums == [2, 3, 1, 3, 1, 2]